Linear Search & Kata Setup
The simplest search algorithm is the linear search.
array [ ]
| |
0 n
search(array, value)
We want a way to search through an array for a value.
array [ array[0] = value? ]
| ^ |
0 | n
|
We traverse the array, checking each value.
array [ array[0] array[1] = value?]
| ^ ^ |
0 | | n
| |
(and so on)
Time Complexity
Recall the three principles of time complexity:
- Growth is with respect to the input.
- Constants are dropped.
- Consider the worst case.
Assuming the worst case, we would have to go from 0 to n, checking each value.
So, the time complexity is
Implementation
fn linear_search<T: PartialEq>(arr: &[T], value: T) -> Option<usize> {
for (i, v) in arr.iter().enumerate() {
if v == &value {
return Some(i);
}
}
None
}
function linearSearch<T>(arr: T[], value: T): number | null {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === value) {
return i;
}
}
return null;
}